#include <vector>
#include <algorithm>
#include <string>
#include <iostream>

using namespace std;

string encode(const string& s){
	string ret;
	int len=s.length();
	for(int i=0;i<len;i++){
		if(i==0){
			if(s.length()==1){
				ret+=s[i];
				return ret;
			}else{
				ret+=s[i] + s[i+1]-'0';
			}
		}else{
			if(i==len-1){
				ret+=s[i]+s[i-1]-'0';
			}else{
				ret+=s[i-1]+s[i]+s[i+1]-'0'-'0';
			}
		}
	}
	//cout<<"\nret"<<ret<<"\n";
	return ret;
}

const string NONE="none";


string process(const string& s,string& ret){
	int len=s.length();
	for(int i=1;i<len;i++){
		char next=s[i]+'0'+'0'-ret[i-1]-ret[i];
		if(next!='0' && next!='1'){
			//cout<<" error at "<<i<<" "<<s<<" "<<ret<<"\n";
			return NONE;
		}
		ret+=next;
	}
	if(ret.length()-len==1 && ret[len]=='0')
		ret.erase(len,1);
	return ret;
}

vector<string>& decode(const string& a){
	vector<string>* ret=new vector<string>(2);
	vector<string>* none2=new vector<string>(2);
	(*none2)[0]=NONE;
	(*none2)[1]=NONE;
	
	int len=a.length();
	string rt;
		switch(a[0]){
			case '3':
			ret=none2;
			break;
			case '2':
			rt="11";
			(*ret)[0]=rt;			
			break;
			case '1':
			rt="01";
			(*ret)[0]=rt;			
			break;
			case '0':
			(*ret)[0]="0";
			(*ret)[1]=NONE;
			break;			
		}
	if(len==1){
		switch(a[0]){
			case '3':
			return *ret;
			case '2':
			case '0':
			(*ret)[1]=NONE;
			return *ret;
			case '1':
			(*ret)[1]="10";
			return *ret;			
		}
	}	
	
	(*ret)[0]=process(a,rt);
	
	if(a[0]=='1'){
		rt="10";
		(*ret)[1]=process(a,rt);
	}else{
		(*ret)[1]=NONE;
	}
	
	return *ret;
}


string vec2string(vector<char>& v){
	vector<char>::iterator it;
	
	string ret;
	for(it=v.begin();it!=v.end();it++){
		ret+=*it;
	}
	return ret;
}

template<class T>
vector<T>& string2vec(string& s){
	vector<T>* v=new vector<T>;
	for(int i=0;i<s.length();i++){
		v->push_back(s[i]);
	}
	return *v;
}

int main(){
	string a="10011101";
	string b="11123221";
	
	vector<char> v=string2vec<char>(a);
	assert(v.size()==a.length());
	string s2=vec2string(v);
	assert(v.size()==s2.length());
	
	string ret=encode(a);
	assert(ret==b);
	assert("1"==encode("1"));
	assert("232"==encode("111"));
	
	vector<string> vv=decode("1");
	cout<<vv[0];
	assert(vv[0]=="01");
	assert(vv[1]=="10");
	vv=decode(b);
	assert(vv[0]==NONE);
	assert(vv[1]==a);
	//cout<<"\n";
	//cout<<b<<" to "<<vv[0]<<","<<vv[1]<<"\n";
}

